
def generate_paren_combos(n):
    """Generate the set of all possible valid arrangements of n pairs
    of parentheses. Note, we have to use sets to store the results
    because we'll end up with duplicates otherwise.
    """
    if n == 0:
        return ""
    curCombos = set(["()"])
    for i in range(1, n):
        combos = set()
        for smaller_combo in curCombos:
            for i in range(len(smaller_combo)):
                combos.add("{}(){}".format(''.join(smaller_combo[:i]), ''.join(smaller_combo[i:])))
        curCombos = combos
    return curCombos

def build_paren_combos(n):
    """Generate the set of all possible valid arrangements of n pairs
    of parentheses. This approach builds all possible strings one
    character at a time, and avoids the duplicate generation of 
    the generate_paren_combos method above.
    """
    combos = []
    charbuf = ['' for _ in range(n*2)]
    return addChar(combos, charbuf, 0, n, n)

def addChar(combos: list, charbuf: list, i: int, left_remaining: int, right_remaining: int):
    """Helper method to recursively build valid arrangements of pairs
    of parentheses. You may imagine this process to be a depth-first
    exploration of the tree of all valid parentheses pairs where the
    left branch always adds an open paren and the right branch a close
    paren.
    """
    if left_remaining == 0 and right_remaining == 0:
        combos.append(''.join(charbuf))
    else:
        if left_remaining > 0:
            charbuf[i] = '('
            addChar(combos, charbuf, i+1, left_remaining - 1, right_remaining)
        if right_remaining > left_remaining:
            charbuf[i] = ')'
            addChar(combos, charbuf, i+1, left_remaining, right_remaining - 1)
    return combos

if __name__ == "__main__":
    
    combos1 = generate_paren_combos(4)
    print(combos1)
    print()
    combos2 = set(build_paren_combos(4))
    print(combos2)
    print()
    print(set.difference(combos2, combos1))

    

    